Codificação Run Length

A codificação run-length é uma técnica para compactar conjuntos de dados esparsos com corridas longas (sequências do mesmo valor). Neste problema, tomaremos como entrada um array 2D (lista de listas) representando uma imagem e o compactaremos usando esta técnica.

Trabalharemos da parte superior esquerda da imagem, compactando sequências de $n$ cópias do mesmo número $c$ em uma única tupla $(n,c)$.

Por exemplo, considere a seguinte pequena matriz 2-D:

[[0, 0, 0],
 [2, 2, 1],
 [1, 1, 1]]

Em forma compactada, isso seria uma lista [(3, 0), (2, 2), (4, 1)] (representando o fato de que, lendo da esquerda para a direita e de cima para baixo, nós primeiro veja uma sequência de 3 0's, depois uma sequência de 2 2's e depois uma sequência de 4 1's).

Como outro exemplo, a seguinte imagem:

é representada por esta matriz:

[[1, 1, 1, 1, 1, 1, 1],
 [1, 0, 0, 0, 0, 0, 1],
 [1, 0, 1, 0, 1, 0, 1],
 [1, 0, 0, 0, 0, 0, 1],
 [1, 0, 1, 1, 1, 0, 1],
 [1, 0, 0, 0, 0, 0, 1],
 [1, 1, 1, 1, 1, 1, 1]]

Na forma comprimida, seria [(8, 1), (5, 0), (2, 1), (1, 0), (1, 1), (1, 0), (1, 1), (1, 0), (2, 1), (5, 0), (2, 1), (1, 0), (3, 1), (1, 0), (2, 1), (5 , 0), (8, 1)].

Defina uma função run_length_encode_2d(array) que recebe um array 2D (lista de listas) como entrada e retorna uma lista de tuplas que representam a versão codificada run-length. Sua função deve ser capaz de lidar com qualquer array 2D de inteiros (não apenas zeros e uns).

Nota:

• Algumas pessoas podem achar mais fácil implementar seu processo de codificação em um array unidimensional primeiro e, em seguida, escrever uma função separada para "nivelar" o array bidimensional em uma única lista de inteiros. Você pode fazer isso se preferir.

Submissão

Quando estiver pronto (depois de ter simulado manualmente e testado em sua própria máquina e estiver convencido de que seu programa fará a coisa certa), faça upload do seu arquivo Python no Problema 3.1 no Gradescope. Lembre de nomear seu arquivo p3_1.py.